/**
 * 
 */
package calculation.passed2;

/**
 * @author Michael
 *
 */
public class Power {

	/**
	 * Pow(x, n)
	 */
	public double powR(double x, int n) {

		assert (!(x == 0 && n < 0));

		if (n < 0) {
			if (n == Integer.MIN_VALUE)
				return 1 / powR(x, -(n + 1)) * (1 / x);
			else
				return 1 / powR(x, -n);
		}
		if (n == 0)
			return 1;
		if (n == 1)
			return x;

		if (n % 2 == 1)
			return powR(x * x, n / 2) * x;
		else
			return powR(x * x, n / 2);
	}

    public double myPow(double x, int n) {
        assert (x != 0 || n >= 0);
        if (n < 0) {
            // pitfall: need to check overflow
            if (n == Integer.MIN_VALUE) {
                return 1 / myPow(x, -(n + 1)) * (1 / x);
            }
            else
                return 1 / myPow(x, -n);
        }
        double result = 1;
        while (n > 0) {
            if ((n & 1) == 1)
                result *= x;
            n = n >> 1;
            x = x * x;
        }
        
        return result;
    }
	
	public double powI(double x, int n) {
		assert (x != 0 || n >= 0);

		double result = 1;
		int e = n;
		if (n < 0) {
			if (n == Integer.MIN_VALUE) {
				e = -(n + 1);
				result *= x;
			} else {
				e = -n;
			}
		}

		while (e > 0) {
			if (e % 2 == 1) {
				result *= x;
			}
			x *= x;
			e = e / 2;
		}

		return n < 0 ? 1 / result : result;
	}

	// O(log(e))? cannot pass the large input, perhaps because of stack memory
	public static double powerRecursive(double x, int e) throws Exception {
		if (x == 0 && e < 0) {
			throw new Exception("e cannot be 0 where x = 0!");
		}

		if (e < 0)
			return 1 / (powerRecursive(x, -e));
		if (e == 0)
			return 1;
		if (e == 1)
			return x;

		if ((e & 0x1) == 1) {
			return powerRecursive(x * x, e >> 1) * x;
		} else {
			return powerRecursive(x * x, e >> 1);
		}

	}

	public static double powerIterative(double x, int e) throws Exception {
		if (x == 0 && e < 0) {
			throw new Exception("e cannot be 0 where x = 0!");
		}
		boolean positive = true;
		if (e < 0) {
			positive = !positive;
			e = -e;
		}
		double result = 1;
		while (e > 0) {
			if ((e & 0x1) == 1) {
				result *= x;
			}
			x *= x;
			e >>= 1;
		}

		return positive ? result : 1.0 / result;
	}

	/**
	 * 
	 */
	public Power() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {

		//		System.out.println(powerRecursive(1.5, -2));
		//		System.out.println(powerRecursive(1.0, 1));
		//		System.out.println(powerRecursive(1.1, 1));
		//		System.out.println(powerRecursive(1.0, 2));
		//		System.out.println(powerRecursive(1.1, 2));
		//		System.out.println(powerRecursive(1.1, 3));
		//		System.out.println(powerRecursive(-1.0, 2));
		//		System.out.println(powerRecursive(-1.0, 3));
		//		System.out.println(powerRecursive(3.58, 4));
		//		System.out.println(powerRecursive(-11.32, 5));
		//		System.out.println(powerRecursive(2, -3));
		//		System.out.println(powerRecursive(-3, -3));
		//		System.out.println(powerRecursive(-2.5, -4));

		System.out.println(powerIterative(1.5, -2));
		System.out.println(powerIterative(1.0, 1));
		System.out.println(powerIterative(1.1, 1));
		System.out.println(powerIterative(1.0, 2));
		System.out.println(powerIterative(1.1, 2));
		System.out.println(powerIterative(1.1, 3));
		System.out.println(powerIterative(-1.0, 2));
		System.out.println(powerIterative(-1.0, 3));
		System.out.println(powerIterative(3.58, 4));
		System.out.println(powerIterative(-11.32, 5));
		System.out.println(powerIterative(2, -3));
		System.out.println(powerIterative(-3, -3));
		System.out.println(powerIterative(-2.5, -4));

	}

}
